Peak index in a mountain array

Time: O(LogN); Space: O(1); easy

Let’s call an array arr a mountain if the following properties hold:

  • arr.length >= 3

  • There exists some i with 0 < i < arr.length - 1 such that:

    • arr[0] < arr[1] < … arr[i-1] < arr[i]

    • arr[i] > arr[i+1] > … > arr[arr.length - 1]

Given an integer array arr that is guaranteed to be a mountain, return any i such that arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1].

Example 1:

Input: A = [0,1,0]

Output: 1

Example 2:

Input: A = [0,2,1,0]

Output: 1

Example 3:

Input: A = [0,10,5,2]

Output: 1

Example 4:

Input: A = [3,4,5,1]

Output: 2

Example 5:

Input: A = [24,69,100,99,79,78,67,36,26,19]

Output: 2

Constraints:

  • 3 <= len(arr) <= 104

  • 0 <= arr[i] <= 106

  • arr is guaranteed to be a mountain array.

1. Binary Search [O(LogN), O(1)]

[1]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def peakIndexInMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        left, right = 0, len(A)

        while left < right:
            mid = left + (right-left) // 2
            if A[mid] > A[mid+1]:
                right = mid
            else:
                left = mid + 1

        return left

[2]:

s = Solution1()

A = [0,1,0]
assert s.peakIndexInMountainArray(A) == 1

A = [0,2,1,0]
assert s.peakIndexInMountainArray(A) == 1

A = [0,10,5,2]
assert s.peakIndexInMountainArray(A) == 1

A = [3,4,5,1]
assert s.peakIndexInMountainArray(A) == 2

A = [24,69,100,99,79,78,67,36,26,19]
assert s.peakIndexInMountainArray(A) == 2